package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/">相交链表 [简单]</a>
 * 给定两个单链表头结点 headA,headB，请找出并返回两个单链表相交的起始节点。如果不想交返回null。
 * 说明：
 * 保证整个链式结构不存在环
 * 1 <= Node.val <= 105
 * 1 <= length <= 3 * 10^4
 * 注意：函数返回结果后，链表必须保持原始结构
 * 进阶：算法时间复杂度O(m+n)，空间复杂度O(1)
 *
 * @author zhenzicheng
 * @date: 2022-06-02 10:21
 */
public class IntersectionOfTwoLinkedLists_160 {

  /**
   * 解法1：
   * 双指针，谁先移动到末尾null就将它指向另一个链表的头，直到headA==headB
   */
  // public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  //   ListNode pA = headA, pB = headB;
  //   while (pA != pB) {
  //     pA = pA == null ? headB : pA.next;
  //     pB = pB == null ? headA : pB.next;
  //   }
  //   return pA;
  // }

  /**
   * 解法2：
   * 双指针，先遍历一遍得到两个链表长度m,n;将长链表移动abs(m-n)位后，和短链表(从头开始)一起遍历直到相等
   */
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA, pB = headB;
    int countA = 0;
    int countB = 0;
    while (pA != null) {
      pA = pA.next;
      countA++;
    }
    while (pB != null) {
      pB = pB.next;
      countB++;
    }

    int x = Math.abs(countA - countB);
    pA = headA;
    pB = headB;
    if (countA > countB) { // A长就多走
      while (x-- != 0) {
        pA = pA.next;
      }
    } else {
      while (x-- != 0) {
        pB = pB.next;
      }
    }

    // 此时遍历直到结尾
    while (pA != null && pB != null) {
      if (pA == pB) {
        return pA;
      }
      pA = pA.next;
      pB = pB.next;
    }
    return null;
  }

}
